비즈네르 암호

3. 원리

예를 들어 'a'를 암호화할 때, 비즈네르 표의 1번 줄에서는 'B', 2번 줄에서는 'C'로 바뀌는데, 이는 카이사르 암호에서 알파벳이 특정 개수만큼 이동하는 것과 같은 원리이다.

3. 1. 비즈네르 표

비즈네르 표는 26개의 알파벳 행으로 구성되며, 각 행은 이전 행에서 한 칸씩 왼쪽으로 순환 이동된 형태이다. 각 행은 서로 다른 카이사르 암호 알파벳에 해당한다.^[25] 표의 첫 번째 행은 평문 알파벳, 첫 번째 열은 키 알파벳을 나타낸다.

이 표에서 'a'는 1번 줄에서는 'B', 2번 줄에서는 'C' 등으로 바뀌는데, 이는 카이사르 암호에서 알파벳이 특정 개수만큼 이동하는 것과 같은 원리이다.

암호화를 할 때는 이 표를 이용하여 평문의 문자와 키워드의 문자를 번갈아 가며 암호화한다. 예를 들어 평문이 `attackatdawn`이고 키워드가 `LEMON`이면, 평문의 첫 글자 `a`는 키워드의 첫 글자 `L`에 해당하는 행에서 찾고, 두 번째 글자 `t`는 키워드의 두 번째 글자 `E`에 해당하는 행에서 찾는 방식이다.

평문:	attackatdawn
키:	LEMONLEMONLE
암호문:	LXFOPVEFRNHR

복호화는 암호화의 반대 과정으로, 키워드의 문자에 해당하는 행에서 암호문의 문자를 찾고, 그 문자가 위치한 열의 첫 글자를 평문으로 사용한다.

3. 2. 암호화

송신자와 수신자는 사전에 키워드(열쇠)를 정한다. 암호화를 위해 타불라 렉타, ''비즈네르 사각형'' 또는 ''비즈네르 표''라고 불리는 알파벳 표를 사용한다. 이 표에는 알파벳이 26번 반복되어 쓰여 있으며, 각 행은 이전 행과 비교하여 순환적으로 왼쪽으로 이동하여 26가지의 카이사르 암호에 해당한다. 암호화 과정의 여러 지점에서 암호는 여러 행 중 하나의 알파벳을 사용하며, 각 지점에서 사용되는 알파벳은 반복되는 키워드에 따라 달라진다.

예를 들어, 평문이 'ATTACKATDAWN'이고 키워드가 'LEMON'이라면, 'L' 행의 'A' 열에 해당하는 'L', 'E' 행의 'T' 열에 해당하는 'X'와 같이 암호화된다. 키워드는 평문의 길이만큼 반복된다. 아래는 그 예시이다.

평문:	attackatdawn
키:	LEMONLEMONLE
암호문:	LXFOPVEFRNHR

오른쪽 그림(비제네르 사각형)을 사용하여 암호화를 수행할 수 있다. 평문을 소문자, 암호문을 대문자로 표시하면, 예를 들어 키를 arm, 평문을 code라고 할 때, 비제네르 사각형에서 a와 c의 교차는 C이고, r과 o는 F, m과 d는 P와 같이 암호문 C, F, P를 얻을 수 있다. 평문이 키보다 긴 경우 키를 반복하여 사용하고, 마지막 평문 e는 a와의 교차로 E가 된다. 즉 평문 "code"는 암호문 "CFPE"가 된다.

3. 3. 복호화

복호화는 암호문의 각 문자에 대해, 키워드의 해당 문자를 사용하여 비즈네르 표에서 평문을 찾는 방식으로 수행된다. 우선 표에서 키에 해당하는 행으로 이동하고, 해당 행에서 암호문 문자의 위치를 찾은 다음, 그 열의 레이블을 평문으로 사용한다.^[3] 예를 들어 설명하면 다음과 같다.

• 암호문: `LXFOPVEFRNHR`
• 키워드: `LEMON`

1. `LEMON`의 첫 글자 'L' 행에서 암호문 'L'을 찾으면 'A' 열에 해당하므로 첫 번째 평문 문자는 'a'이다.^[3]

2. `LEMON`의 두 번째 글자 'E' 행에서 암호문 'X'를 찾으면 'T' 열에 해당하므로 두 번째 평문 문자는 't'이다.^[3]

이와 같은 방식으로 나머지 암호문도 복호화할 수 있다.

오른쪽 그림(비즈네르 사각형)을 사용하여 복호화를 수행할 수도 있다. 예를 들어 키가 'arm'이고 암호문이 'CFPE'일 때, 복호화 과정은 다음과 같다.

1. 비즈네르 사각형에서 'a' 행에서 'C'의 위치를 찾고, 거기서 위로 거슬러 올라가면 맨 위 행의 문자는 'c'이므로 평문은 'c'이다.

2. 'r' 행에서 'F'를 찾아 위로 거슬러 올라가면 'o'를 얻는다.

3. 'm' 행에서 'P'를 찾아 위로 거슬러 올라가면 'd'를 얻는다.

4. 평문이 키보다 길 경우 키를 반복하여 사용하므로, 'a' 행에서 'E'를 찾아 위로 거슬러 올라가면 'e'를 얻는다.

따라서 암호문 'CFPE'는 평문 'code'로 복호화된다.

3. 4. 수학적 설명

비즈네르 암호는 모듈러 연산을 사용하여 대수적으로 표현할 수 있다. 먼저, A부터 Z까지의 알파벳을 0부터 25까지의 숫자로 나타낸다. (A=0, B=1, ..., Z=25) 그리고 26으로 나눈 나머지를 구하는 모듈러 연산을 활용한다.

암호화 과정은 다음과 같다. 평문의 각 문자를 $M\_i$, 키의 각 문자를 $K\_i$라고 할 때, 암호문 $C\_i$는 다음과 같이 계산된다.

:$C\_i\; =\; (M\_i\; +\; K\_i)\; \backslash mod\; 26$

즉, 평문의 각 문자에 해당하는 숫자와 키의 각 문자에 해당하는 숫자를 더한 후, 26으로 나눈 나머지를 구하면 암호문의 각 문자에 해당하는 숫자가 된다.

복호화 과정은 다음과 같다. 암호문의 각 문자를 $C\_i$, 키의 각 문자를 $K\_i$라고 할 때, 평문 $M\_i$는 다음과 같이 계산된다.

:$M\_i\; =\; (C\_i\; -\; K\_i)\; \backslash mod\; 26$

즉, 암호문의 각 문자에 해당하는 숫자에서 키의 각 문자에 해당하는 숫자를 뺀 후, 26으로 나눈 나머지를 구하면 평문의 각 문자에 해당하는 숫자가 된다.

예를 들어, 평문 'T'를 키 'E'로 암호화하는 경우를 생각해보자. T는 19, E는 4에 해당하므로, (19 + 4) mod 26 = 23 이 되고, 23은 X에 해당하므로 암호문은 'X'가 된다. 반대로 암호문 'X'를 키 'E'로 복호화하는 경우, (23 - 4) mod 26 = 19 가 되고, 19는 T에 해당하므로 평문 'T'를 얻을 수 있다.

4. 해독법

비즈네르 암호는 글자 빈도를 숨겨 빈도 분석을 어렵게 만들지만, 키의 반복적인 특성 때문에 해독될 수 있다. 암호 분석가가 키의 길이 ''n''을 정확하게 추측하면, 암호문은 ''n''개의 엇갈린 카이사르 암호로 취급되어 각각 해독될 수 있다. 키 길이는 가능한 모든 ''n'' 값을 무차별 대입하여 테스트하거나, 카시스키 검사 및 프라이드먼 검사를 통해 결정할 수 있다.

키의 길이가 알려지면, 암호문을 키의 각 문자에 해당하는 여러 열로 나눌 수 있다. 각 열은 단일 카이사르 암호로 암호화된 평문으로 구성된다. 카이사르 키(쉬프트)는 해당 열에 사용된 비즈네르 키 문자이다. 카이사르 암호를 해독하는 데 사용되는 방법과 유사하게, 암호문의 각 문자를 해독할 수 있다.
빈도 분석 과정1. 같은 문자의 나열을 찾는다. 문자열이 길수록 좋다.

2. 문자 나열의 간격을 센다.

3. 발견된 문자 간격의 최대공약수를 통해 키의 문자 수를 추정한다.

4. 암호문의 간격이 최대공약수의 값인 문자끼리는 같은 행(단순한 시저 암호)이 사용되었음을 알 수 있다.

5. 암호문의 해당 간격 문자들의 빈도를 그래프로 나타내면 평문의 빈도 분석과 비슷하면서도 다른 형태가 된다.

6. 문자를 약간 이동시켜 평문의 빈도 분석 결과와 거의 같게 만들어 비즈네르 암호를 해독한다.

"반복되는 문자열"은 평문이 같을 때, 같은 비즈네르 격자의 행에 해당하는 부분에서 생성된다. "간격을 센다"는 것은 평문이 같았던 경우, 사용된 키는 그 간격의 약수여야 하기 때문이다. 키의 문자 수를 알면, 이전 방식의 해독법으로 해독할 수 있다는 것이 비즈네르 암호의 가장 큰 결점이다. 시저 암호는 키가 26개뿐이므로 모두 조사할 수 있지만, 비즈네르 암호는 연속된 문자열이 아니므로 모두 조사해도 의미 있는 단어가 되기 어렵다.

비즈네르 암호는 키 길이가 알려져 있거나 추측할 수 있다면 키 제거를 통해서도 해독이 가능하다. 암호문을 키 길이만큼 엇갈리게 자기 자신에서 빼면, 평문을 자기 자신에서 뺀 결과와 같아진다. 이 방법은 평문에 추정 가능한 단어가 있어야 키를 복구할 수 있다는 조건이 있다.

4. 1. 카시스키 검사

4. 2. 프리드먼 검사 (카파 검사)

• ''c''는 알파벳의 크기(영어의 경우 26)
• ''N''은 텍스트의 길이
• ''n''₁부터 ''n''_''c''는 관측된 암호문 문자 빈도를 정수로 나타낸 값

4. 3. 빈도 분석

• "반복되는 문자열"은 평문이 같을 때, 같은 비즈네르 격자의 행에 해당하는 부분에서 생성된다.
• "간격을 센다"는 것은 평문이 같았던 경우, 사용된 키는 그 간격의 약수여야 하기 때문이다.
• 키의 문자 수를 알면, 옛날 방식의 해독법으로 해독할 수 있다는 것이 비즈네르 암호의 가장 큰 결점이다.
• 시저 암호는 키가 26개뿐이므로 모두 조사할 수 있지만, 비즈네르 암호는 연속된 문자열이 아니므로 모두 조사해도 의미 있는 단어가 되기 어렵다.

4. 4. 키 제거

5. 변형

비즈네르 암호에는 여러 가지 변형이 존재한다.

비즈네르 암호는 표에 매우 강한 대칭성(선형성)이 있어 해독의 단서가 된다. 이를 해결하기 위해 표 안의 문자를 무작위로 배치하는 방법이 고안되었다. 이 방법은 카시스키 검사의 유효성을 현저히 감소시켜 종이와 펜만으로는 거의 해독할 수 없게 만들었다. 하지만 표 작성과 해독에 시간이 오래 걸리고, 비즈네르 암호가 해독 불가능하다고 여겨졌기 때문에 널리 사용되지는 않았다. 무작위 배치 방식은 현대 암호에서 S-box 구현에 활용되어 선형 해독법, 차분 해독법에 대한 내성을 강화한다.

비즈네르 자신이 1586년에 발표한 무작위 배치 표는 '비즈네르 표'라고 불리지는 않는다. 무작위 배치는 해독을 어렵게 만들지만, 확률론적으로 취약한 표가 만들어질 수 있으므로 취약성 검정이 필요하다.

5. 1. 러닝 키 암호

먼저 `GO` 키로 암호화한 다음 `CAT` 키로 다시 암호화하는 것은 하나의 키를 다른 키로 암호화하여 생성된 키로 한 번 암호화하는 것과 같다.^[1]

이는 `attackatdawn`을 `IOZQGH`로 암호화하여 원래 예제와 같은 암호문을 생성하는 것으로 보여준다.^[1]

키 길이가 서로소이면 개별 키 길이가 증가함에 따라 실질적인 키 길이는 기하급수적으로 증가한다. 예를 들어, 10, 12, 15자 길이의 키의 실질적인 길이는 60에 불과하지만, 8, 11, 15자 길이의 키의 실질적인 길이는 1320이다. 이 실질적인 키 길이가 암호문보다 길면 러닝 키 변형과 마찬가지로 프리드먼 검정과 카시스키 검정에 대한 면역성을 갖게 된다.^[1]

진정으로 무작위적인 키를 사용하고, 암호화된 메시지보다 길이가 같거나 더 길며, 한 번만 사용하는 경우 비즈네르 암호는 이론적으로 해독 불가능하다. 그러나 이 경우에는 암호가 아니라 키가 암호화 강도를 제공하며, 이러한 시스템은 사용된 암호와 관계없이 원타임 패드 시스템으로 통칭된다.^[1]

5. 2. 보퍼트 암호

5. 3. 그롱스펠트 암호

5. 4. 자동 키 암호

참조

_[1] 서적 Cryptography, Information Theory, and Error-Correction: A handbook for the 21st Century https://books.google[...] John Wiley & Sons
_[2] 서적 Everyday Cryptography https://books.google[...] Oxford University Press
_[3] 서적 Cryptography: The Science of Secret Writing https://books.google[...] Courier Corporation
_[4] 간행물 Vigenère Cipher https://crypto.inter[...] Crypto Corner
_[5] 서적 Würzburger Humanismus Narr Verlag 2015
_[6] 서적 Polygraphiae, libri sex … http://lcweb2.loc.go[...] Johann Haselberg 1518
_[7] 문서 https://www.digitale[...]
_[8] 서적 Traicté des Chiffres, ou Secretes Manieres d'Escrire http://gallica.bnf.f[...] Abel l'Angelier 1586
_[9] 서적 La Cifra del Sig. Giovan Battista Belaso … https://bibdig.museo[...] 1553
_[10] 서적 The Codebreakers: The Story of Secret Writing Simon & Schuster
_[11] 학술지 A new cipher code https://babel.hathit[...] 1917-01-27
_[11] 학술지 Letter to the Editor: Cipher codes https://babel.hathit[...] 1917-03-03
_[11] 학술지 Letter to the Editor: A new cipher https://babel.hathit[...] 1917-04-14
_[11] 학술지 The ciphers of Porta and Vigenère: The original undecipherable code, and how to decipher it https://babel.hathit[...] 1921-10-01
_[12] 서적 State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures https://archive.org/[...] Springer
_[13] 서적 The Code Book Anchor Books, Random House
_[14] 웹사이트 Codes, Ciphers, & Codebreaking http://www.vectorsit[...]
_[15] 서적 The Codebreakers: The Story of Secret Writing Simon & Schuster
_[16] 웹사이트 Crypto Overview, Perfect Secrecy, One-time Pad http://www.ics.uci.e[...] 2004-09-28
_[17] 간행물 Vernam-Vigenère cipher https://www.britanni[...] Encyclopedia Britannica
_[18] 서적 Die Geheimschriften und die Dechiffrir-Kunst https://books.google[...] E.S. Mittler und Sohn 1863
_[19] 학술지 Secret, or cypher writing https://books.google[...] 1854-08-11
_[19] 학술지 Mr. Thwaites's cypher https://books.google[...] 1854-09-01
_[19] 서적 Passages from the Life of a Philosopher https://archive.org/[...] Longman 1864
_[20] 웹사이트 Weekly list of patents sealed. … 1727. John Hall Brock Thwaites, Bristol – Improvements in apparatus to facilitate communication by cypher. https://babel.hathit[...]
_[20] 서적 Thwaites, John Hall Brock, of Bristol, dentist. ''Improvements in apparatus to facilitate the communication by cypher''. Application dated August 7, 1854. (No. 1727). https://books.google[...] The Mechanics' Magazine 1855-03-03
_[21] 학술지 Secret or cypher writing https://babel.hathit[...] 1854-09-15
_[21] 학술지 Mr. Thwaites's cypher https://babel.hathit[...] 1854-10-06
_[22] 서적 Mr. Babbage's Secret: The Tale of a Cypher and APL https://books.google[...] Prentice Hall
_[23] 서적 Encyclopedia of Cryptography and Security https://archive.org/[...] Springer
_[24] 학술지 The Bar Statistics
_[25] 웹사이트 Lab exercise: Vigenere, RSA, DES, and Authentication Protocols http://courses.umass[...]